<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,200分)- 字符串拼接（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>给定 M&#xff08;0 &lt; M ≤ 30&#xff09;个字符&#xff08;a-z&#xff09;&#xff0c;从中取出任意字符&#xff08;每个字符只能用一次&#xff09;拼接成长度为 N&#xff08;0 &lt; N ≤ 5&#xff09;的字符串&#xff0c;</p> 
<p>要求相同的字符不能相邻&#xff0c;计算出给定的字符列表能拼接出多少种满足条件的字符串&#xff0c;</p> 
<p>输入非法或者无法拼接出满足条件的字符串则返回0。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>给定的字符列表和结果字符串长度&#xff0c;中间使用空格(&#34; &#34;)拼接</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>满足条件的字符串个数</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">abc 1</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">3</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">给定的字符为a,b,c&#xff0c;结果字符串长度为1&#xff0c;可以拼接成a,b,c&#xff0c;共3种</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">dde 2</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">2</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">给定的字符为dde&#xff0c;结果字符串长度为2&#xff0c;可以拼接成de,ed&#xff0c;共2种</td></tr></tbody></table> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>根据用例2的说明来看&#xff0c;本题是要求解的是&#xff1a;不重复的指定长度的排列。且本题还增加了一个条件&#xff0c;即排列中相邻元素不能相同。</p> 
<p></p> 
<p>本题的基础是求解排列。关于排列的求解可以看下&#xff1a;</p> 
<p><a href="https://blog.csdn.net/qfc_128220/article/details/127286788?csdn_share_tail&#61;%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22127286788%22%2C%22source%22%3A%22qfc_128220%22%7D" title="LeetCode - 46 全排列_全排列 46 力扣-CSDN博客">LeetCode - 46 全排列_全排列 46 力扣-CSDN博客</a></p> 
<p></p> 
<p>了解的排列的求解后&#xff0c;我们就可以进一步了解不重复的排列求解&#xff0c;具体可以看下&#xff1a;</p> 
<p><a href="https://fcqian.blog.csdn.net/article/details/127292846" rel="nofollow" title="LeetCode - 47 全排列 II_leetcode 全排列2-CSDN博客">LeetCode - 47 全排列 II_leetcode 全排列2-CSDN博客</a></p> 
<p></p> 
<p>而本题只需要在这两题的基础增加&#xff1a;排列中相邻元素不能相同即可。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

void (async function () {
  let [s, n] &#61; (await readline()).split(&#34; &#34;);
  n &#61; parseInt(n);

  function getResult() {
    if (s.length &lt; n) {
      // 无法拼接出满足条件的字符串
      return 0;
    }

    for (let c of s) {
      // 输入非法
      if (c &lt; &#34;a&#34; || c &gt; &#34;z&#34;) return 0;
    }

    // 排序cArr&#xff0c;可以方便后面求解全排列时&#xff0c;进行树层去重
    const cArr &#61; [...s].sort();
    return dfs(cArr, -1, 0, new Array(cArr.length).fill(false), 0);
  }

  /**
   * 全排列求解
   * &#64;param {*} cArr 基于cArr数组求解全排列
   * &#64;param {*} pre 排列最后一个字符在cArr中的位置
   * &#64;param {*} level 排列的长度
   * &#64;param {*} used used[i] 用于标记 cArr[i] 元素是否已使用
   * &#64;param {*} count 符号要求的排列有几个
   * &#64;returns count
   */
  function dfs(cArr, pre, level, used, count) {
    // 当排列长度到达n&#xff0c;则是一个符合要求的排列
    if (level &#61;&#61; n) {
      // 符合要求的排列个数&#43;1
      return &#43;&#43;count;
    }

    for (let i &#61; 0; i &lt; cArr.length; i&#43;&#43;) {
      // 每个字符只能用一次
      if (used[i]) continue;

      // 相同的字符不能相邻&#xff0c; pre指向前面一个被选择的字符的在cArr中的位置&#xff0c;i指向当前被选择的字符在cArr中的位置
      if (pre &gt;&#61; 0 &amp;&amp; cArr[i] &#61;&#61; cArr[pre]) continue;

      // 树层去重(去除重复排列)
      if (i &gt; 0 &amp;&amp; cArr[i] &#61;&#61; cArr[i - 1] &amp;&amp; !used[i - 1]) continue;

      used[i] &#61; true;
      count &#61; dfs(cArr, i, level &#43; 1, used, count);
      used[i] &#61; false;
    }

    return count;
  }

  console.log(getResult());
})();
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Arrays;
import java.util.Scanner;

public class Main {
  static String s;
  static int n;

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    s &#61; sc.next();
    n &#61; sc.nextInt();

    System.out.println(getResult());
  }

  public static int getResult() {
    if (s.length() &lt; n) {
      // 无法拼接出满足条件的字符串
      return 0;
    }

    char[] cArr &#61; s.toCharArray();

    for (char c : cArr) {
      // 输入非法
      if (c &lt; &#39;a&#39; || c &gt; &#39;z&#39;) return 0;
    }

    // 排序cArr&#xff0c;可以方便后面求解全排列时&#xff0c;进行树层去重
    Arrays.sort(cArr);
    return dfs(cArr, -1, 0, new boolean[cArr.length], 0);
  }

  /**
   * 全排列求解
   *
   * &#64;param cArr 基于cArr数组求解全排列
   * &#64;param pre 排列最后一个字符在cArr中的位置
   * &#64;param level 排列的长度
   * &#64;param used used[i] 用于标记 cArr[i] 元素是否已使用
   * &#64;param count 符号要求的排列有几个
   * &#64;return count
   */
  public static int dfs(char[] cArr, int pre, int level, boolean[] used, int count) {
    // 当排列长度到达n&#xff0c;则是一个符合要求的排列
    if (level &#61;&#61; n) {
      // 符合要求的排列个数&#43;1
      return &#43;&#43;count;
    }

    for (int i &#61; 0; i &lt; cArr.length; i&#43;&#43;) {
      // 每个字符只能用一次
      if (used[i]) continue;

      // 相同的字符不能相邻&#xff0c; pre指向前面一个被选择的字符的在cArr中的位置&#xff0c;i指向当前被选择的字符在cArr中的位置
      if (pre &gt;&#61; 0 &amp;&amp; cArr[i] &#61;&#61; cArr[pre]) continue;

      // 树层去重(去除重复排列)
      if (i &gt; 0 &amp;&amp; cArr[i] &#61;&#61; cArr[i - 1] &amp;&amp; !used[i - 1]) continue;

      used[i] &#61; true;
      count &#61; dfs(cArr, i, level &#43; 1, used, count);
      used[i] &#61; false;
    }

    return count;
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
s, n &#61; input().split()
n &#61; int(n)


# 全排列求解
def dfs(cArr, pre, level, used, count):
    &#34;&#34;&#34;
    全排列求解
    :param cArr: 基于cArr数组求解全排列
    :param pre: 排列最后一个字符在cArr中的位置
    :param level: 排列的长度
    :param used: used[i] 用于标记 cArr[i] 元素是否已使用
    :param count: 符号要求的排列有几个
    :return: count
    &#34;&#34;&#34;
    # 当排列长度到达n&#xff0c;则是一个符合要求的排列
    if level &#61;&#61; n:
        # 符合要求的排列个数&#43;1
        count &#43;&#61; 1
        return count

    for i in range(len(cArr)):
        # 每个字符只能用一次
        if used[i]:
            continue

        # 相同的字符不能相邻&#xff0c; pre指向前面一个被选择的字符的在cArr中的位置&#xff0c;i指向当前被选择的字符在cArr中的位置
        if pre &gt;&#61; 0 and cArr[i] &#61;&#61; cArr[pre]:
            continue

        # 树层去重(去除重复排列)
        if i &gt; 0 and cArr[i] &#61;&#61; cArr[i - 1] and not used[i - 1]:
            continue

        used[i] &#61; True
        count &#61; dfs(cArr, i, level &#43; 1, used, count)
        used[i] &#61; False

    return count


# 算法入口
def getResult():
    if len(s) &lt; n:
        # 无法拼接出满足条件的字符串
        return 0

    for c in s:
        if c &lt; &#39;a&#39; or c &gt; &#39;z&#39;:
            # 输入非法
            return 0

    cArr &#61; list(s)
    # 排序cArr&#xff0c;可以方便后面求解全排列时&#xff0c;进行树层去重
    cArr.sort()

    return dfs(cArr, -1, 0, [False] * len(cArr), 0)


# 算法调用
print(getResult())
</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

#define MAX_SIZE 31

char s[MAX_SIZE];
int s_len;
int n;

/*!
 * 全排列求解
 * &#64;param pre 排列最后一个字符在cArr中的位置
 * &#64;param level 排列的长度
 * &#64;param used used[i] 用于标记 s[i] 元素是否已使用
 * &#64;param count 符号要求的排列有几个
 * &#64;return count
 */
int dfs(int pre, int level, int used[], int count) {
    // 当排列长度到达n&#xff0c;则是一个符合要求的排列
    if (level &#61;&#61; n) {
        // 符合要求的排列个数&#43;1
        return &#43;&#43;count;
    }

    for (int i &#61; 0; i &lt; s_len; i&#43;&#43;) {
        // 每个字符只能用一次
        if (used[i]) continue;

        // 相同的字符不能相邻&#xff0c; pre指向前面一个被选择的字符的在s中的位置&#xff0c;i指向当前被选择的字符在s中的位置
        if (pre &gt;&#61; 0 &amp;&amp; s[i] &#61;&#61; s[pre]) continue;

        // 树层去重(去除重复排列)
        if (i &gt; 0 &amp;&amp; s[i] &#61;&#61; s[i - 1] &amp;&amp; !used[i - 1]) continue;

        used[i] &#61; 1;
        count &#61; dfs(i, level &#43; 1, used, count);
        used[i] &#61; 0;
    }

    return count;
}

int cmp(const void *a, const void *b) {
    return *((char *) a) - *((char *) b);
}

int getResult() {
    int i &#61; 0;
    while (s[i] !&#61; &#39;\0&#39;) {
        // 输入非法
        if (s[i] &lt; &#39;a&#39; || s[i] &gt; &#39;z&#39;) return 0;
        i&#43;&#43;;
    }

    s_len &#61; i;

    if (s_len &lt; n) {
        // 无法拼接出满足条件的字符串
        return 0;
    }

    // 排序s&#xff0c;可以方便后面求解全排列时&#xff0c;进行树层去重
    qsort(s, i, sizeof(char), cmp);

    int used[MAX_SIZE] &#61; {0};
    return dfs(-1, 0, used, 0);
}

int main() {
    scanf(&#34;%s&#34;, s);
    scanf(&#34;%d&#34;, &amp;n);

    printf(&#34;%d\n&#34;, getResult());

    return 0;
}</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>